How many apples can you put into the basket

Time: O(NLogN); Space: O(N); easy

You have some apples, where arr[i] is the weight of the i-th apple.

You also have a basket that can carry up to 5000 units of weight.

Return the maximum number of apples you can put in the basket.

Example 1:

Input: arr = [100,200,150,1000]

Output: 4

Explanation:

  • All 4 apples can be carried by the basket since their sum of weights is 1450.

Example 2:

Input: arr = [900,950,800,1000,700,800]

Output: 5

Explanation:

  • The sum of weights of the 6 apples exceeds 5000 so we choose any 5 of them.

Constraints:

  • 1.1 <= len(arr) <= 10^3

  • 2.1 <= arr[i] <= 10^3

[1]:

class Solution1(object):
    """
    Time: O(NLogN)
    Space: O(N)
    """
    def maxNumberOfApples(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        LIMIT = 5000
        arr.sort()
        result, total = 0, 0

        for x in arr:
            if total+x > LIMIT:
                break
            total += x
            result += 1

        return result

[2]:

s = Solution1()
arr = [100,200,150,1000]
assert s.maxNumberOfApples(arr) == 4
arr = [900,950,800,1000,700,800]
assert s.maxNumberOfApples(arr) == 5